package com.yuan.algorithms.arithmetic_1;

/*
 主要思想：
 x^n = 1 (n=0)
 x^n = (x^(n/2))^2 (n>0，n为偶数)
 x^n = (x^(n/2))^2*x (n>0，n为奇数)
 */
import java.util.Scanner;

public class 递归_x的n次幂 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int x = sc.nextInt();
			int n = sc.nextInt();
			System.out.println(power(x, n));
			
			System.out.println(pow(x, n));
		}

	}

	private static long pow(int x, int n) {
		int temp = x;
		long pow = 1;
		for (int i = 0; i < n/2; i++) {
			pow *= temp;
		}
		pow *= pow;
		if (n%2==1) {
			pow *= temp;
		}
		return pow;
	}
	/**
	 * 递归求x的n次幂
	 * @param x 底数
	 * @param n 幂的次数
	 * @return x^n
	 */
	private static long power(int x, int n) {
		long y;
		if (n==0) {
			y = 1;
		}else {
			y = power(x, n/2);
			y *= y;
			if (n%2==1) {
				y *= x;
			}
		}
		return y;
	}

}
